import sys
import functools
import itertools
import random
import heap

__all__ = ['Graph', 'Edge', 'Node', 'topological_sort', 'post_order_sort', 'get_reachable', 'strongly_connected_components', 'shortest_path', 'generate_rand_edges']

@functools.total_ordering
class Node:

    def __init__(self, key, value=None):
        self._key = key
        self._value = value

    def set_value(self, value):
        self._value = value

    def value(self):
        return self._value

    def key(self):
        return self._key

    def __str__(self):
        valueStr = ""
        if self._value is not None:
            valueStr = ": " + str(self._value)
        return str(self._key) + valueStr

    def __repr__(self):
        if self._value is None:
            return "Node({})".format(self._key)
        else:
            return "Node({}, {})".format(self._key, self._value)

    def __eq__(self, other):
        return self._key == other.key()

    def __lt__(self, other):
        return self._key < other.key()

    def __hash__(self):
        return self._key.__hash__()

class Edge:
         
    def __init__(self, endpoint1: Node, endpoint2: Node, isDirected: bool, value=None):
        self._value = value
        self._endpoint1 = endpoint1
        self._endpoint2 = endpoint2
        self._isDirected = isDirected

    def is_directed(self):
        return self._isDirected

    def set_value(self, value):
        self._value = value

    def value(self):
        return self._value

    def endpoints(self):
        return (self._endpoint1, self._endpoint2)

    def __str__(self):
        valueStr = ""
        if self._value is not None:
            valueStr = ": " + str(self._value)
        if self._isDirected:
            return "({} --> {}){}".format(str(self._endpoint1), str(self._endpoint2), valueStr)
        else:
            return "({} -- {}){}".format(str(self._endpoint1), str(self._endpoint2), valueStr)

    def __eq__(self, other):
        otherEndpoint1, otherEndpoint2 = other.endpoints()
        if self._endpoint1 == otherEndpoint1 and self._endpoint2 == otherEndpoint2:
            return True
        elif self._isDirected and self._endpoint1 == otherEndpoint2 and self._endpoint2 == otherEndpoint1:
            return True
        return False

    def __hash__(self):
        return hash(self._endpoint1.__hash__() + self._endpoint2.__hash__())


class Graph(object):
    """A graph consisting of a set of nodes and a set of edges. Each
    node and each edge may have an associated value, which may be 
    updated. The graph may be directed or undirected.
    """

    def __init__(self, nodes, edges):
        """Graph initializer. Builds a graph from a set of nodes and edges."""
        if len(edges) > 0:
            self._isDirected = next(iter(edges)).is_directed()
        for e in edges:
            if e.is_directed() != self._isDirected:
                raise Exception("edge types are inconsistent")

        self._nodes = nodes
        self._edges = edges
        self._initAdjacencyList()

    def _initAdjacencyList(self):
        self._adjacencyList = {node: set() for node in self._nodes}
        for edge in self._edges:
            endpoint1, endpoint2 = edge.endpoints()
            self._adjacencyList[endpoint1].add(edge)

            if not self._isDirected:
                self._adjacencyList[endpoint2].add(edge)

    def is_directed(self):
        return len(self._edges) == 0 or self._isDirected

    def nodes(self):
        """Returns an iterable over the nodes of the graph."""
        return (n for n in self._nodes);

    def edges(self):
        """Returns an iterable over the edges of the graph."""
        return (e for e in self._edges)

    def edges(self, source: Node):
        """Returns an iterable over all of the set of dest nodes
        {dest | (source, dest) exists in self._edges}
        """
        return (e for e in self._adjacencyList[source])

    def reverse(self):
        """Returns a graph with all edges reversed in direction,
        or simply returns this graph if it is not a directed graph.
        """
        if not self.is_directed() : return self
        return (Graph(self._nodes, 
                      [Edge(e.endpoints()[1], e.endpoints()[0], True, e.value()) for e in self._edges]))

    def __str__(self):
        nodeStr = '\n'.join((str(node) for node in self._nodes))
        edgeStr = '\n'.join(
            ("+++ From {} +++\n{}".format(
                str(node), 
                '\n'.join(str(edge) for edge in self.edges(node)))
             for node in self._nodes))

        return "{}\n{}\n{}\n{}".format("-----Nodes-----", nodeStr, "-----Edges-----", edgeStr)

def has_cycle(g: Graph):
    """Returns True if the specified graph has a cycle, or False otherwise."""
    result = False
    counter = [0]
    for node in g.nodes():
        node.x_entered = None
        node.x_exited = None

    def detectCycle(source: Node):
        foundCycle = False
        if source.x_exited is not None:
            return False
        if source.x_entered is not None:
            return True
        
        source.x_entered = counter[0]
        counter[0] += 1
        edgesFromSource = g.edges(source)
        for edgeFromSource in edgesFromSource:
            _, dest = edgeFromSource.endpoints()
            if detectCycle(dest):
                foundCycle = True
                break

        source.x_exited = counter[0]
        counter[0] += 1
        return foundCycle

    for node in g.nodes():
        if detectCycle(node):
            result = True
            break

    for node in g.nodes():
        del node.x_entered
        del node.x_exited

    return result

def topological_sort(g: Graph):
    """Returns a list of the nodes in the specified graph in topological
    sort order. If no topological sort is possible, raises an Exception.
    """
    if not g.is_directed:
        raise Exception("Cannot topologically sort an undirected graph")
    if has_cycle(g):
        raise Exception("Cannot topologically sort a graph with a cycle")

    sortedNodes = post_order_sort(g)
    sortedNodes.reverse()
    return sortedNodes

def post_order_sort(g: Graph):
    """Returns a list of the nodes in the specified graph in the order
    that they are post processed by a depth-first-search."""
    sortedNodes = []

    for node in g.nodes():
        sortedNodes += _explore(g, node, False)

    for node in sortedNodes:
        del node.x_visited

    return sortedNodes


def get_reachable(g: Graph, source: Node):
    """Returns a list of the nodes in the given graph that are reachable from the
    given source node, in the order that they are post-processed by depth-first
    search.
    """
    return _explore(g, source)


def _explore(g: Graph, source: Node, doClearReachableFlag: bool = True):
    """Helper function that returns a list of nodes in g reachable from source,
    in order that they are post-processed by depth-first search.
    """
    reachableNodes = []
    if not hasattr(source, 'x_visited'): 
        source.x_visited = True
        edgesFromSource = g.edges(source)
        for edgeFromSource in edgesFromSource:
            _, dest = edgeFromSource.endpoints()
            _explore(g, dest, False)
        reachableNodes.append(source)

    if doClearReachableFlag:
        for node in reachableNodes:
            del node.x_visited
            
    return reachableNodes


def strongly_connected_components(g: Graph):
    """Returns a DAG, where each node is a strongly connected component in g."""

    # Performing a depth-first search on a given source node is guaranteed to 
    # discover all nodes in the source node's strongly component, but unless
    # it is in a sink strongly connected component (one that has no path to 
    # another strongly connected component) the DFS will also reveal nodes that
    # aren't in it's SCC. Our algorithm therefore looks like this:
    # Let G' be the subgraph consisting soley of nodes whose SCC has not been
    # identified.
    # while G' is not empty
    #   find a node s in a sink SCC in G'
    #   perform a dfs on s, and add s and all of the nodes reachable from s
    #   to a new SCC. 
    #   remove those nodes from G'
    #
    # To assist in finding nodes in snk SCCs, we first perform a DFS on the
    # reversed graph G_r and record the post numbers for each node. The node
    # in G' with the highest of these post numbers is guaranteed to be in a 
    # sink SCC.

    if not g.is_directed():
        raise Exception("Strongly connected components are only applicable to directed graphs.")

    stronglyConnectedComponents = []
    sccConnections = set()
    sinkOrderedNodes = post_order_sort(g.reverse())
    sinkOrderedNodes.reverse()
    
    for source in sinkOrderedNodes:
        reachableNodes = _explore(g, source, False)
        if len(reachableNodes) > 0:
            scc = Node(len(stronglyConnectedComponents), reachableNodes)
            for node in reachableNodes:
                node.x_scc = scc
            stronglyConnectedComponents.append(scc)

    # Now build the DAG by recording the connections between various SCCs
    for node in g.nodes():
        scc = node.x_scc
        connectedNodes = g.edges(node)
        for connectedNode in connectedNodes:
            connectedScc = connectedNode.x_scc
            sccConnections.add(Edge(scc, connectedScc, True))

    for node in g.nodes():
        del node.x_visited
        del node.x_scc

    return Graph(stronglyConnectedComponents, sccConnections)

def shortest_path(g: Graph, source: Node):
    """Returns a dict mapping the length of the shortest path from
    the specified source node to each node reachable from that source node.
    """

    distances = {}
    # we want a min priority queue
    q = heap.PriorityQueueInverter(heap.PriorityQueue())
    q.insert(source, 0)

    while len(q) > 0:
        node, dist = q.pop()
        if node in distances.keys():
            continue
        distances[node] = dist
        nextEdges = g.edges(node)
        for nextEdge in nextEdges:
            _ , nextNode = nextEdge.endpoints()
            if nextNode in distances.keys():
                continue
            edgeLen = nextEdge.value()
            nextDist = dist + edgeLen
            # note: nextNode may already be in the queue. Rather than check
            # for this condition and call decrease_key, which would require
            # a special heap implementation, we'll simply insert the node 
            # again with it's new value. The node may end up being inserted
            # once per incoming edge, but the instance that is popped first
            # will represent the shortest path, and will be the one recorded
            # in the distances dict
            q.insert(nextNode, nextDist)

    return distances

def generate_rand_edges(nodes, isDirected: bool, minValue: int = None, maxValue: int = None):
    valueIter = None
    if minValue is None or maxValue is None:
        valueIter = (None for _ in range(sys.maxsize))
    else:
        valueIter = (random.randrange(minValue, maxValue+1) for _ in range(sys.maxsize))
    edges = set([])
    for i, node in enumerate(nodes):
        sampleSpace = list(range(i)) + list(range(i+1, len(nodes)))
        numSamples = random.randrange(0, len(nodes))
        for dest in random.sample(sampleSpace, numSamples):
            edges.add(Edge(node, nodes[dest], isDirected, valueIter.__next__()))

    return edges


if __name__ == "__main__":
    
    isDirected = True;
    nodes = [Node(i) for i in range(2)]
    edges = generate_rand_edges(nodes, isDirected, 0, 100)
    g = Graph(nodes, edges)
    print(g)
    distances = shortest_path(g, nodes[0])
    print()
    print(distances)
    print()
    
    g_r = g.reverse()
    print(g_r)

    print(has_cycle(g))

    print()
    print(strongly_connected_components(g))

   

    
